#include<iostream>
#include<vector>
using namespace std;
/*
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
解题思路：
首先应该明确树形结构,该树形结构的深度是是digits的字符串个数,每一层的节点数是digits单个字符对应的字符串个数

*/

//全局变量
string path;
vector<string> result;
vector<string> digitsMap{
    "","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"
};
void trackbacking(string digits,int index)
{
    //递归终止条件,当遍历到index==digits.size()时终止
    if(index==digits.size())
    {
        result.push_back(path);
        return;
    }
    //首先提取出当前的数字
    int digit = digits[index]-'0';
    string map = digitsMap[digit];
    //遍历digitsMap[digit]
    //由于每一层都是单独不相同的集合，所以无需考虑元素重复的问题
    //使用for加上回溯完成树的每一层节点的遍历
    for(int i=0;i<map.size();i++)
    {
        path.push_back(map[i]);
        trackbacking(digits,index+1);//向下递归,往后遍历digits
        //回溯
        path.pop_back();
    }
}
vector<string> letterCombinations(string digits) {
    trackbacking(digits,0);
    return result;
}
int main()
{
    cout<<"enter digits:"<<endl;
    string digits;
    cin>>digits;
    vector<string> result = letterCombinations(digits);
    for(int i=0;i<result.size();i++)
    {
        for(int j=0;j<result[i].size();j++)
            cout<<result[i][j];
        cout<<endl;
    }
    return 0;
}